package demo.algorithm;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。
 * 许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符，即【增删改】。
 * 编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。
 * <p>
 * 用途： 模糊查询；DNA分析 ；拼字检查 ；语音辨识 ；抄袭侦测；相似度判断；
 * 
 * @author junying.han
 *
 */
public class Levenshtein {

    private static Logger logger = LoggerFactory.getLogger(Levenshtein.class);

    /**
     * 比较两个字符串的相识度
     * <p>
     * 核心算法：用一个二维数组记录每个字符串是否相同，如果相同记为0，不相同记为1，每行每列相同个数累加
     * 则数组最后一个数为不相同的总数，从而判断这两个字符的相识度
     *
     * @param str1
     * @param str2
     * @return
     */
    public static int levenshteinDistinceIgnoreCase(String str1, String str2) {
        int length1 = str1.length();
        int length2 = str2.length();
        if (length1 == 0) {
            return length2;
        }
        if (length2 == 0) {
            return length1;
        }
        // 矩阵
        int[][] dif = new int[length1 + 1][length2 + 1];
        // 初始化第一列
        for (int i = 0; i <= length1; i++) {
            dif[i][0] = i;
        }
        // 初始化第一行
        for (int i = 0; i <= length2; i++) {
            dif[0][i] = i;
        }
        int temp; // 记录相同字符,在某个矩阵位置值的增量,不是0就是1
        for (int index1 = 1; index1 <= length1; index1++) {
            // 遍历str
            char char1 = str1.charAt(index1 - 1);
            // 去匹配target
            for (int index2 = 1; index2 <= length2; index2++) {
                char char2 = str2.charAt(index2 - 1);
                // 忽略大小写
                if (char1 == char2 || char1 == char2 + 32 || char1 + 32 == char2) {
                    temp = 0;
                } else {
                    temp = 1;
                }
                // 左边+1,上边+1, 左上角+temp取最小
                dif[index1][index2] = Math.min(dif[index1 - 1][index2 - 1] + temp,
                        Math.min(dif[index1 - 1][index2] + 1, dif[index1][index2 - 1] + 1));
            }
        }
        return dif[length1][length2];
    }

    public static int levenshtein(String str1, String str2) {
        // 计算两个字符串的长度。
        int len1 = str1.length();
        int len2 = str2.length();
        // 建立上面说的数组，比字符长度大一个空间
        int[][] dif = new int[len1 + 1][len2 + 1];
        // 赋初值
        for (int a = 0; a <= len1; a++) {
            dif[a][0] = a;
        }
        for (int a = 0; a <= len2; a++) {
            dif[0][a] = a;
        }
        // 计算两个字符是否一样，计算左上的值
        int temp;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    temp = 0;
                } else {
                    temp = 1;
                }
                // 取三个值中最小的
                dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1, dif[i - 1][j] + 1);
            }
        }
        return dif[len1][len2];
    }

    /**
     * DNA分析 拼字检查 语音辨识 抄袭侦测
     * 
     * @createTime 2012-1-12
     */
    public static void printLevenshtein(String str1, String str2) {
        // 计算两个字符串的长度。
        int len1 = str1.length();
        int len2 = str2.length();
        // 建立上面说的数组，比字符长度大一个空间
        int[][] dif = new int[len1 + 1][len2 + 1];
        // 赋初值
        for (int a = 0; a <= len1; a++) {
            dif[a][0] = a;
        }
        for (int a = 0; a <= len2; a++) {
            dif[0][a] = a;
        }
        // 计算两个字符是否一样，计算左上的值
        int temp;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    temp = 0;
                } else {
                    temp = 1;
                }
                // 取三个值中最小的
                dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1, dif[i - 1][j] + 1);
            }
        }
        System.out.println("字符串\"" + str1 + "\"与\"" + str2 + "\"的比较");
        // 取数组右下角的值，同样不同位置代表不同字符串的比较
        System.out.println("差异步骤：" + dif[len1][len2]);
        // 计算相似度
        float similarity = 1 - (float) dif[len1][len2] / Math.max(str1.length(), str2.length());
        System.out.println("相似度：" + similarity);
    }

    // 得到最小值
    private static int min(int... is) {
        int min = Integer.MAX_VALUE;
        for (int i : is) {
            if (min > i) {
                min = i;
            }
        }
        return min;
    }

    /**
     * 获取两字符串的相似度
     */
    public static float getSimilarityRatio(String str, String target) {
        int max = Math.max(str.length(), target.length());
        return 1 - (float) levenshteinDistinceIgnoreCase(str, target) / max;
    }

    /**
     * 比较两个字符串的相似度算法（Levenshtein Distance）
     * <p>
     * Levenshtein Distance，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括：【增删改
     * 】将一个字符替换成另一个字符，插入一个字符，删除一个字符。 编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein
     * Distance。
     * <p>
     * 算法原理：
     * 
     * 该算法的解决是基于动态规划的思想，具体如下：
     * <li>设 s 的长度为 n，t 的长度为 m。如果 n = 0，则返回 m 并退出；如果 m=0，则返回 n 并退出。否则构建一个数组 d[0..m,
     * 0..n]。
     * <li>将第0行初始化为 0..n，第0列初始化为0..m。
     * <li>依次检查 s 的每个字母(i=1..n)。
     * <li>依次检查 t 的每个字母(j=1..m)。
     * <li>如果 s[i]=t[j]，则 cost=0；如果 s[i]!=t[j]，则 cost=1。将 d[i,j] 设置为以下三个值中的最小值：
     * <li>紧邻当前格上方的格的值加一，即 d[i-1,j]+1
     * <li>紧邻当前格左方的格的值加一，即 d[i,j-1]+1
     * <li>当前格左上方的格的值加cost，即 d[i-1,j-1]+cost
     * <li>重复3-6步直到循环结束。d[n,m]即为莱茵斯坦距离。
     */
    @Test
    public void testLevenshteinDistance() {
        String a = "recover failed with max retry count,will not try again. txid:globalTransactionId:6ef97153-de88-343e-af81-4d39385d4fe4,branchQualifier:d26d925b-6594-3c30-8198-983cc37853f8, status:3,retried count:31,transaction content:{\"createTime\":1585271415597,\"lastUpdateTime\":1585272385000,\"participant\":{\"invocat||recover failed with max retry count,will not try again. txid:globalTransactionId:6ef97153-de88-343e-af81-4d39385d4fe4,branchQualifier:d26d925b-6594-3c:";
        String b = "recover failed with max retry count,will not try again. txid:globalTransactionId:fde7fde9-1dfe-337b-83a5-ad37ec6da9a0,branchQualifier:14253f43-fc12-369b-bb38-e1863746a558, status:3,retried count:31,transaction content:{\"createTime\":1585266137518,\"lastUpdateTime\":1585267090000,\"participant\":{\"invocat||recover failed with max retry count,will not try again. txid:globalTransactionId:fde7fde9-1dfe-337b-83a5-ad37ec6da9a0,branchQualifier:14253f43-fc12-36:";
        System.out.println("相似度：" + getSimilarityRatio(a, b));
        a = "abcdefg";
        for (int i = 0; i < a.length(); i++) {
            b = a.substring(0, i);
            logger.info("src = {}, tar = {},  LevenshteinDistance = {}", a, b, levenshteinDistinceIgnoreCase(a, b));
        }
    }
}
